This invention relates to the field of network engineering and analysis, and in particular to a method and system for managing traffic flow in a network for efficient link utilization and resilient performance under failure conditions.
Routing algorithms are generally structured to select a route for traffic between nodes of a network based on the relative ‘cost’ associated with each potentially available route. For example, an Interior Gateway Protocol (IGP) is commonly used on Internet Protocol (IP) networks to determine the optimal route from a source node to a destination node based on a total cost of each available route, using one or more metrics for determining such costs. Example Interior Gateway Protocols include Routing Information Protocol (RIP), Open Shortest Path First (OSPF), and Intermediate System to Intermediate System (IS-IS) protocols.
Typically, when a link is added to a network, the metric is assigned at the interface to the link, reflecting the relative cost/impact of using the link. For example, if the link is a high capacity link, the relative impact of sending a packet over the link is generally slight, compared to the impact of sending that same packet over a link with very limited capacity. By assigning low costs to high capacity links, and high costs to low capacity links, more traffic will generally be routed by such cost/metric based routing algorithms to the high capacity links, thereby avoiding congestion on the low capacity links.
FIG. 1A illustrates an example network with links A-V between nodes of the network. FIG. 1B illustrates an example set of metrics associated with each link A-V, and FIG. 1C illustrates an example set of routes and composite metrics associated with each. In this example, only four traffic flow demands are presented for consideration, from San Francisco 110 to each of: New York 120 (SF-NY, 60 Mb/s), Chicago 130 (SF-CH, 40 Mb/s), Atlanta 140 (SF-AT, 40 Mb/s), and Houston 150 (SF-HO, 20 Mb/s). The composite metric for the routes is determined in this example as the sum of the metrics of the links along the route; other techniques for determining a composite metric based on link metrics may also be used, such as a composite that is based on the metric of each link and the number of links (hops) along the route.
In FIG. 1C, five sample routes are illustrated for the traffic from SF 110 to NY 120. The first route, using links D (SF to AT), L (AT to DC), and Q (DC to NY), has a composite metric of 58 (44+8+6); the second route, A-E, has a composite metric of 50 (10+40), the third route, A-F-N-O, has a composite metric of 42 (10+16+4+12), and so on. Based on these composite metrics, the 60 Mb/s traffic from SF to NY is preferably routed along the route A-F-N-O, the route with the lowest composite metric. In like manner, the 40 Mb/s traffic from SF to CH is preferably routed along A-F-N; the 20 Mb/s traffic from SF to HO along route A-C; and the 40 Mb/s traffic from SF to AT along route A-F-H.
It is significant to note that in this example, each of the preferred routes include the link A. Therefore all of the traffic from SF to NY, CH, HO, and AT will travel over link A. With the routing in this example, link A will have 160 Mb/s of load. Whether or not link A can efficiently handle this load is based on the capacity of link A. If link A's capacity is 320 Mb/s, for example, its utilization is 50%; if link A's capacity is under 160 Mb/s, link A is over-utilized, and the traffic demand will not be satisfied. Network managers strive to avoid over-utilized links, and try to minimize the link utilization on each of the links to assure efficient traffic flow across the network.
Traffic engineering addresses techniques for optimizing network performance, including the configuration of resources of a network to provide effective and efficient traffic flow through the network. In “Internet Traffic Engineering by Optimizing OSPF weights” at IEEE INFOCOM 2000, B. Fortz and M. Thorup presented the concept of adjusting the metrics assigned to links from their initially assigned values so as to cause devices that use an existing routing protocol (OSPF) to select different routes than those selected based on the default metric values, to achieve an overall desired traffic flow through the network. Extensions for dealing with varying traffic and transient link failures were proposed by Fortz et al. (B. Fortz and M. Thorup. “Optimizing OSPF/IS-IS weights in a changing world”, IEEE JSAC 2001) and Nucci et al. (Nucci et al. “IGP link weight assignment for transient link failures”, ITC 2003) respectively. Currently in the commercial arena, Cariden Technologies (www.cariden.com) and WANDL (www.wandl.com) have competing solutions for IGP metric optimization.
Techniques that provide for global optimization of networks are well suited for an initial installation of a network, and for ongoing management of small networks, but are generally poorly suited for routine ongoing maintenance of large networks. Often, relatively minor changes to a network can have a major effect on determining the optimal solution in a large network, due to the cascading of change effects. For example, a relatively minor reduction in a link's metric may ‘attract’ a large number of routes that previously had relatively equivalent costs, and other metrics may need to be adjusted to subsequently attract some of the traffic from this now-overloaded link. That is, a minor improvement in network performance may require a substantial number of individual metric changes, as the conventional processes strive to tune the network for truly optimal performance.
It would be advantageous to provide improvements to network performance in an incremental manner, preferably with minimal changes to the configuration of devices in the network. It would also be advantageous to identify and address the links that are in violation of a maximum link utilization threshold, as well as the links whose failure will introduce a significant number of threshold violations.
These advantages, and others, can be realized by a metric tuning technique that optimizes the maximum link utilization of a set of links incrementally. Changes to the metric are constrained to be metric increases to divert routes from select links, thereby minimizing the number of changes required to achieve the optimization by avoiding the potential cascade of changes caused by attracting routes to a link. An interactive user interface is provided to allow a user to specify limits and constraints, and to select the sets of links to be addressed, including, for example, only the links that exceed a given link utilization threshold, the links having the highest link utilizations, the links having the highest failure effect, and so on. This incremental optimization technique is also used to optimize network resiliency by minimizing the network degradation caused by the failure of one or more links.
Throughout the drawings, the same reference numerals indicate similar or corresponding features or functions. The drawings are included for illustrative purposes and are not intended to limit the scope of the invention.